Design Top-K over Rolling Windows

Understanding the problem

LinkedIn hands this out more than any other design, and it shows up in two framings. One is product-facing: the top-K most-shared URLs or trending hashtags, served on the feed as "trending now." The other is infrastructure-facing: the top-K most-frequent error signatures across a fleet of services, served on an internal observability dashboard. Same machine underneath. You count items as events stream past, and you keep the K heaviest hitters fresh over several windows at once: the last 5 minutes, the last hour, the last day, and all-time.

Start with the textbook single-machine answer: a hash map of counts and a heap. Now watch the interviewer turn up the volume until it falls apart. The interviewer cares more about that escalation than the prompt. You have to rebuild the thing as a distributed, streaming system without losing the plot on memory, throughput, or freshness. The ranking behind the feed, behind people-search suggestions, behind trending content, behind ad leaderboards, is this same shape. Get it right once and you have the throughline behind half of LinkedIn's product.

Anchor on the numbers before any boxes. Treat the firehose as a few billion counted engagement events a day. Call it five billion, which averages out to roughly 58,000 events a second and spikes a few times that at peak, so plan for around 150,000 a second. Each event is tiny: an item id, a timestamp, a little context, on the order of 100 bytes. So the stream is heavy in event count and light in bytes, about 15 MB a second at peak. The number of distinct items is its own axis. A day surfaces on the order of 10 million distinct URLs or error signatures, and that set grows without bound as the window stretches toward all-time.

The LinkedIn angle

LinkedIn is more likely to hand you this prompt than any other, and it grades the transition harder than the final picture. A weak loop draws the distributed diagram immediately and never explains why. A strong loop starts with the hash map and heap on one machine, says plainly where it breaks, and earns every distributed piece against a specific limit. LinkedIn invented Kafka and open-sourced both Samza and Pinot to serve exactly this workload, so the interviewer often knows the real production answer cold. Vague hand-waving about "using a stream processor" lands badly against someone who has run one.

Functional requirements

Propose a tight scope and let the interviewer redirect. The core is ingesting a stream of "item seen" events, and answering one read: give me the top-K items for a named window, ranked by count. The windows are the interesting part, so name them up front.

Non-functional requirements

Reason through each requirement and attach a target, because here the relaxations are what make the design tractable. The biggest one comes first. Reads are eventually consistent and the counts can be approximate. A trending list that is two seconds stale fools nobody, and a count that is off by a fraction of a percent never changes which items sit at the top. State that up front. It is the permission slip for every cheap structure later in this design; a candidate insisting on exact counts over a rolling all-time window is solving a problem nobody asked about.

Ingestion is the hard requirement. The pipeline has to swallow the full firehose at peak without dropping events on the floor and without letting a traffic spike back up into the producers. Read latency should sit comfortably under a second, since a ranking feeds a page render. Availability matters more on the read path than on ingestion: if ingestion stalls for a few seconds the rankings just freeze briefly, which is survivable, but a query that times out blocks a page. The windows must roll. A 5-minute window means the last 5 minutes counted from this instant, so midnight is irrelevant and old data has to age out cleanly.

• ~5B/day Engagement events. ~58K/sec average, ~150K/sec peak, ~100 bytes each.
• ~10M Distinct items/day. Unbounded as the window grows toward all-time.
• Top 100 Per window. 5 min, 1 hr, 1 day, all-time, served in parallel.
• Approximate Read consistency. A few seconds stale and slightly off is fine.

The set-up

Core entities

Name the few objects the system moves around before drawing anything. Three carry this design:

One split matters most: the raw events versus the derived rankings. The events are a write-once firehose nobody queries directly. The rankings are a tiny derived view, a few hundred rows per window, read constantly. Those two have opposite profiles, so they want opposite storage. The raw events land in a cheap append-only log partitioned by item id, which keeps every event for a given item on one partition. The rankings live in a fast store sized for low-latency reads. Naming that partition key matters, because partitioning by item id is the decision that makes every later merge step cheap.

API

The interface is small. Producers push events, and readers ask for a ranking by window. The write path is fire-and-forget, the read path is a single parameterized query.

# Producers emit events (fire-and-forget, batched in practice)
POST /events
  body: { itemId, timestamp, context }
  -> 202 Accepted              # ack = durably queued; counting happens downstream
 
# Readers ask for a ranking
GET /topk?window=5m&k=100      # window in {5m, 1h, 1d, all}
  -> { window, asOf, items: [ { itemId, count }, ... ] }   # count is an estimate

High-level design

Build it as two lanes that share one log. A fast lane counts the stream live and serves approximate rankings within seconds. A slow lane reprocesses the same events in bulk and overwrites closed windows with exact numbers. Readers only ever talk to the served rankings, so they never feel which lane produced them. Each box is coded by role: blue for people, violet for our services, amber for the streams, green for storage. The walkthrough below tags each component the same way.

1) Capture the firehose. Member activity fires "item seen" events at the Event collector, a thin stateless service that does two things and no more. It batches events to amortize network cost, and it hashes each one to a partition by item id before publishing to Kafka. We reach for a durable log here instead of calling the counter directly because a log buffers. When a peak of around 150,000 events a second hits, or a consumer slows down, events pile up safely on the log instead of backing pressure up into the producers. The ack a producer gets means "durably queued," not "counted," and that distinction is what lets the counting layer fall behind for a moment without losing data. How many partitions the log carries caps how many counting workers can run in parallel, which is the sharding question deep dive four takes on.

2) Count it live. The Stream processor runs one worker per Kafka partition, and because we keyed the log by item id, each worker owns a disjoint slice of items end to end. A worker reads its partition and maintains, per short time bucket, a compact counting structure plus a heap of the current top-K. Every few seconds it flushes the merged top-K for each window to the Top-K store. The naive thing would be a giant hash map with one exact counter per distinct item: around a gigabyte for a day of 10 million distinct items, unbounded as the all-time window stretches. That memory blow-up is the first bottleneck, and the count-min sketch in deep dive two replaces the hash map with about 54 KB of counters that never grow with the item count.

3) Serve the read. A Reader hits the Query service with a window and a K. The service reads the precomputed ranking straight out of the Top-K store and returns it. Nothing is sorted at query time and nothing touches the raw stream. A ranking is a few hundred rows, so this is a single cheap lookup. It stays well under the sub-second target even while 150,000 events a second roar past on the other side of the system. The four windows are precomputed in parallel, so asking for the 5-minute list costs the same as asking for all-time. Reads and writes never contend, because they touch entirely different structures: the firehose writes sketches, the reader touches only the served rankings. Keeping that served view fresh is the pressure the two-lane split in deep dive five manages.

4) Reconcile in bulk. In parallel, every event is archived to the Raw event log, roughly 500 GB a day of 100-byte events on the cheapest storage there is. The Batch recompute job replays that archive on a schedule to compute exact top-K for windows that have closed, then overwrites the speed layer's estimates for those windows. This is the slow, accurate half of a two-lane design: the live lane is fast and approximate, the batch lane is slow and exact, and they meet in the served store. Nothing on the read path waits for the batch job, since its numbers land in the same Top-K store the reader already polls. Deep dive five builds out why you want both lanes and when each one wins.

Size the firehose

We pinned the firehose at roughly 5 billion events a day, about 58,000 a second on average and 150,000 at peak, each event near 100 bytes. Two sizing questions fall out of that. The first is parallelism. A single stream worker maintaining sketches absorbs on the order of tens of thousands of events a second before it falls behind. To carry 150,000 a second with headroom for an uneven partition, we want something like 32 to 64 Kafka partitions, each owned by one worker. Partition count caps counting throughput, so we size it for peak plus a margin, and we can't raise it cheaply later without reshuffling which items live where.

The second question is memory, which is where this design pays off. Each count-min sketch is about 54 KB, and a worker keeps a handful per granularity. That's roughly 60 live minute-sketches, 24 hour-sketches, a slice of day-sketches, and one all-time sketch: on the order of 100 sketches and a few megabytes per worker. Across 64 workers that is a few hundred megabytes of counters for the entire company's firehose, against the hundreds of gigabytes an exact hash map would burn on the all-time window alone. The one thing that grows without bound is the archive: 500 GB a day, about 180 TB a year, which object storage holds for pennies and the batch lane reads only in bulk.

• Peak ingest: ~150K/sec. ~15 MB/sec of 100-byte events at peak, against a ~58K/sec average. We size for 32 to 64 Kafka partitions so counting throughput keeps headroom above the spike.
• Counter memory: ~54 KB/sketch. About 100 sketches and a few MB per worker, a few hundred MB across the fleet, versus hundreds of GB for an exact all-time hash map.
• Archive growth: ~500 GB/day. Around 180 TB a year of append-only events on cheap object storage. It is the rebuild source for the batch lane, never a query path.
• Served view: A few hundred rows. Per window, read in well under a second. Tiny and read-heavy, sized for low-latency lookups, not for holding the firehose.

Technology choices

Every box so far is a category. In the room, name a real tool for each and be ready for the failure question, because that is where this round goes.

• The Event collector is a stateless service behind a load balancer, the same shape as any web tier. It holds nothing a request needs, so any instance serves any event and a dying one just drops out of rotation with no state to recover. Its one piece of logic that matters is the partition hash, computed on item id, so the decision of which item lands on which downstream worker is made once, here, at the edge. We keep it stateless on purpose: the moment a collector held counts, we could no longer scale it horizontally or lose an instance without losing data. The failure question is a traffic spike. The answer is that it batches events and the durable log behind it absorbs the burst, so a collector never drops anything while the counting layer catches up.
• Kafka is the log, and naming it at LinkedIn is not a guess: LinkedIn built Kafka for exactly this kind of pipeline. Partitions are the unit of parallelism, one consumer per partition, so partition count caps how many stream workers can run in parallel. The failure question is a consumer crash, and the answer is offset replay: each worker records how far it has read, so a restarted worker rewinds to its last committed offset and reprocesses. That replay is also why counting has to tolerate reprocessing the same event, which the bucketed sketches handle by being rebuilt from the log rather than mutated blindly.
• The Stream processor is Flink, or Samza, which LinkedIn wrote for this workload. Headline whichever name the room knows; the role is the same. It gives you three things you'd otherwise hand-build: per-key state (each worker's sketches and heaps for its slice of items), windowing (buckets roll on a schedule), and checkpointing (in-memory state survives a restart). The failure question is a worker crash. The worker reloads its last checkpoint and replays its Kafka partition from the last committed offset; since sketches are rebuilt from the log, reprocessing after a crash lands on the same counts. The thing it must never do is keep an exact count of every distinct item in memory, which is the trap deep dive one walks into.
• The Top-K store is Pinot, LinkedIn's real-time OLAP store, or any fast key-value store keyed by window. We reach for a store tuned for reads here because the served rankings have the opposite profile from the firehose. They're a few hundred rows per window, rewritten every few seconds but read on every page load. Pinot fits because it ingests directly from Kafka and answers top-N group-by queries in single-digit milliseconds using pre-aggregated column indexes, which is exactly the read this design serves. The failure question is a hot read on a trending list during a spike. The answer is that the rankings are tiny and cacheable, so the query service can hold the current top-K in memory and refresh it on the flush interval instead of hitting the store.
• The Raw event log is cheap object storage like S3, or extended Kafka retention feeding a data lake. We pick object storage because the bytes are huge, write-once, and almost never read back: 500 GB a day of 100-byte events that only the batch lane scans, which a database would price dearly. Append-only and durable is the exact profile of an audit trail, and it doubles as the rebuild source if every derived ranking burned down at once. The failure question is cost, and the math answers it. A year of history is 180 TB, and in object storage that runs to pennies next to keeping it hot. The batch lane reads it in bulk on a schedule, never on a user's request.

The LinkedIn angle

Name LinkedIn's real stack and the round shifts in your favor, but keep it to the public shape. Kafka is the ingestion log, a stream processor like Samza maintains the live aggregates, and Pinot serves the top-N queries, ingesting from Kafka and answering in milliseconds. LinkedIn has written publicly about all three. You can say "I would serve the rankings out of a real-time OLAP store like Pinot, fed from Kafka, the way LinkedIn does this in production" without claiming internal detail you do not have. Naming the systems shows you know the domain; staying at the architecture level keeps you honest about what is public.

Potential deep dives

Most of the interview signal lives here. The interviewer picks one or two and pushes hard. These are the ones LinkedIn leans on, and the first two are the heart of the round.

1) Why not just a hash map and a heap on one machine?

Start here, every time. The exact answer takes only a few lines. Keep a hash map from item id to count, and a min-heap of size K holding the current top-K. On each event, increment the item's count, and if the new count beats the smallest in the heap, push it in and evict the loser. Reading the top-K is just reading the heap. For one window on one machine, this is correct, fast, and the right place to begin.

So the single machine breaks for two distinct reasons, and they push in different directions. Memory pushes you toward an approximate structure that does not store one entry per item. Throughput and availability push you toward many machines. The next three dives take those one at a time: shrink the per-window memory with a sketch, roll the windows, then spread the work across shards.

2) The count-min sketch: counting in kilobytes

The memory problem comes entirely from storing one counter per distinct item. A count-min sketch throws that requirement out. It is a fixed-size grid of counters that estimates any item's count without ever storing the item, and its size does not grow with the number of distinct items at all. For a top-K leaderboard, where you only care about the heavy hitters, its one weakness barely bites.

Picture a grid with d rows and w columns of integer counters, all starting at zero, plus d independent hash functions, one per row. To record an item, hash it once per row to pick one column in that row, and increment those d counters. To estimate the item's count, hash it the same way and take the minimum of those d counters. The minimum is the trick: every counter can only be inflated by other items that happened to collide into the same cell, so the smallest of the d cells is the least polluted estimate. The sketch therefore never underestimates. It only ever overestimates, and only when collisions pile up.

The error is bounded, and the math is worth getting exactly right because the interviewer may ask. With width w = ⌈e / ε⌉ and depth d = ⌈ln(1/δ)⌉, the estimate exceeds the true count by at most ε · N with probability at least 1 − δ. Here N is the total number of events counted, e is Euler's number, ε is the error fraction you pick, and δ is the chance of blowing past the bound. Work a concrete case. Choose ε = 0.001 and δ = 0.01. Then w = ⌈e / 0.001⌉ = 2,719 columns and d = ⌈ln(100)⌉ = 5 rows. That is about 13,600 counters. At 4 bytes each, the whole sketch is roughly 54 KB.

The LinkedIn angle

The count-min sketch is the answer LinkedIn wants here. What sets it apart is naming the boundary before anyone asks for it. The sketch is approximate, and that is fine, because a trending list only needs the heavy hitters and they tower over the error floor. Now say where it would be wrong: a sketch's number never goes on an invoice or a billing report, where the count has to be exact. That fast-versus-exact split runs through every counting system LinkedIn builds. Knowing which side of it a given requirement lands on is the whole difference between reciting a data structure and engineering with one.

The reason a sketch survives the distributed system, and not just the single machine, is one property: it is linear. Two sketches with the same dimensions and the same hash functions add element by element, and the sum is exactly the sketch you would have built by feeding both streams into one. That single fact is what makes both windowing and sharding work, which is the next two dives.

3) Rolling windows: bucket, merge, expire

A rolling window means "the last 5 minutes as of right now," and it keeps moving. The lazy approach, one running sketch per window that you add to forever, falls apart the moment you need to remove old data, because a count-min sketch cannot safely subtract. Decrementing cells corrupts the minimum estimate for every item that shares a cell. So you never subtract. You bucket time instead, and you expire whole buckets.

Keep one sketch (and its heap) per small time bucket, say one minute. The current minute's bucket takes all the increments. A window query sums the spans that cover it: the 5-minute window is the element-wise sum of the last 5 minute-sketches, and since sketches are linear, that sum keeps the same error guarantee. Summing 5 small sketches is cheap. Summing 1,440 of them for a one-day window is not, so roll them up in a hierarchy: fold each hour's 60 minute-sketches into one hour-sketch and 24 of those into a day-sketch. Then accumulate the day level into a single ever-growing all-time sketch.

4) Sharding the firehose and merging per-shard top-K

One machine cannot take 150,000 events a second forever, so spread the stream across many workers. The way you spread it decides whether merging the results is trivial or lossy. Treat it as a real decision and reason it out.

The merge approximation is worth stating precisely, because it is a favorite probe. With item-hash sharding there is no summation error, since each item is counted in one place. The only error is truncation: an item that no shard ranked highly enough to emit cannot appear in the global top-K. Emitting K' well above K shrinks that risk to near zero for the heavy hitters, which is all top-K needs. Set K' = 5K as a default and tighten it if the interviewer pushes on the boundary.

The LinkedIn angle

Expect the interviewer to camp on the merge. It is where someone who has read about top-K and someone who has built it part ways. Shard by item id, not by event. Each item's count lives on one shard, so the global merge is a union with no summation error; the only cost is a hot key on the top item, which an upstream combiner absorbs. Walk that and you have named the tradeoff, picked a side with a reason, and killed the follow-up about the hottest item before it is asked. Raise the failure yourself, every time.

5) The two lanes: approximate now, exact later

The speed layer runs fast and lands a little imprecise. Sometimes a little imprecise will not do. An observability dashboard driving an incident page wants the real top error signature, and a billing-adjacent leaderboard wants exact counts. Any window old enough to have stopped moving might as well be exact. So pair the live sketch path with a batch path that recomputes the truth from the archived log and overwrites closed windows.

The exact-versus-approximate split is the spine of the whole design, so make it explicit. Live windows are served approximate, because seconds-fresh and a fraction of a percent off is what trending needs. Closed windows are served exact, because they have stopped moving and the truth is cheap to compute once. The reader never chooses; the served store simply holds the best answer available for each window, and the batch or replay path upgrades estimates to exact as windows age out.

6) What breaks in production?

Once the happy path holds, a senior interviewer circles to the operational questions. Each answer leans on a decision already made earlier.

• A hot key pins one shard. The most-trending item routes all its events to a single worker under item-hash sharding. The local combiner from deep dive four is the defense. Each collector pre-sums one second of a hot item into a single (item, count) message, so the owning shard sees a trickle of partial sums instead of a flood of raw events. Counting is cheap; only the routing was hot, and the combiner fixes the routing.
• Late events arrive after their window closed. A phone that engaged offline syncs an hour later. The speed layer has already moved on, so its number for that window is a little low. The batch or replay lane is the answer: it reprocesses the archived log with a grace period and folds stragglers into the corrected, exact window. A watermark, the processor's deadline for how long it waits for late data, decides when the speed layer calls a window done; anything later than the watermark is the batch lane's job.
• A stream worker crashes. It restarts, reloads its last checkpoint, and replays its Kafka partition from the last committed offset. Because the sketches are rebuilt from the log rather than mutated in place, reprocessing the same events after a crash converges to the same counts. The window freezes for a few seconds of catch-up and then is current again. No data is lost, because the log still holds it.
• The all-time window's error floor creeps up. Sketch error scales with total events N, and all-time N only grows. If the tail of the all-time ranking starts looking noisy, widen that one sketch (more columns lowers ε). Or serve all-time from the exact batch numbers, which is reasonable since all-time barely moves minute to minute. Pay the extra memory only on the window that needs it.
• Consistency under reads. Every read is eventually consistent by design, and that is a feature, not a gap. The served ranking can lag the firehose by the flush interval, a few seconds, and two readers a moment apart might see slightly different lists near the boundary. For trending content and error leaderboards, that is invisible and acceptable. Saying so plainly, and saying why it is safe, is what the requirement was set up to let you cash in.

The LinkedIn angle

This design is a gift for showing an operational mindset, which is exactly what LinkedIn's senior bar wants. Notice how every failure resolves to a choice you already made: the local combiner absorbs hot keys, the batch lane absorbs late events, offset replay absorbs crashes, the eventual-consistency relaxation absorbs read skew. Walk two or three of them without being prompted, in concrete terms ("the hottest URL hits one shard, here is why it does not melt"), and a passing round turns into a strong one. The gap is between someone who has been paged by a streaming system at 4am and someone who has only diagrammed one.

What is expected at each level

That is a lot of surface area. Here is how much you need to land, by the level you are interviewing for. This is LinkedIn's signature design, so the bar on it is calibrated and the leveling committee weighs it heavily.

Mid (entry IC)

Breadth-led, about 80/20. Reach a working end-to-end pipeline: a durable log, a stream worker that counts, a served store the reader queries, and the windows named. You should start from the single-machine hash map and heap, and recognize the memory problem when the all-time window is raised, even if the interviewer leads you to the sketch. The bar: a complete firehose-to-ranking path you can explain, with the single-machine limit found together.

Senior

Now depth, roughly 60/40, and this is the level that most often turns on this design. You raise approximate-and-eventually-consistent before being asked, reach the count-min-sketch-plus-heap answer on your own, and name its error floor and why the heavy hitters clear it. You shard by item id with a reason, handle the hot key with a combiner, and explain the rolling-window buckets without being walked there. The bar: a near-optimal approximate top-K where you found the memory, merge, and hot-key issues yourself.

Staff+

Depth leads as scope widens, roughly 40/60. Expect the two-lane split defended with numbers, and kappa-style replay weighed against a separate batch layer. Expect the sketch-linearity argument that makes both windowing and sharding sound, late-event handling with watermarks, and a clear story for when exact beats approximate per requirement. You are reasoning about how the system degrades and heals, and you are driving. The bar: you run the session, the interviewer redirects rather than rescues, and every approximation is a choice you can defend.